Communications networks for voice communications (telephone), and also other forms of communications, usually consist of a number of nodes (or stations) interconnected by transmission links. This is because it is impractical to provide a transmission link from every user to every other user if the number of users is large. Therefore, the users are connected to a switch (or switches) which is used to provide a connection to any other user when such a connection is needed. If the number of users is very large and they are widely dispersed, it is more practical to provide more than one switch. The multiple switches are interconnected by communications links to form a network. The interconnecting links between switches provide additional economy by permitting a large number of calls or messages to share a common transmission facility (this is called multiplexing).
In a very large communications network, it is usually impractical to provide enough transmission links to directly connect every switching node to every other switching node. Hence, it is common practice for the telephone call, or other form of communications, to be passed from node to node through tandem connections of the transmission links in order to establish a path between the node to which the originating user is connected and the node to which the destination user is connected. Some of the nodes serve as access switching nodes through which users access the network, while others serve only as tandem switching nodes to establish connection through more distant nodes, and still others provide both functions. The switching nodes permit a most efficient utilization of transmission facilities by allowing the interconnecting transmission facilities to be shared among a large number of users. In large networks which have several nodes, the switches permit an alternate path (through different tandem nodes) to be selected when a portion (either a switch or a connecting link) of a particular path between two users is fully loaded. The switches can also permit selection of alternate paths when some of the nodes or transmission facilities are inoperative due to equipment failures, natural disasters, or acts of war.
A communications network to support recovery from natural disasters or to support wartime military operations must have the capability to provide survival of the communications even when major portions of the network have been destroyed. One of the best methods of enhancing such wartime communications survivability is to provide and make use of a large number of nodes, each with connecting links to many other nodes. This will provide a large number of paths through different combinations of interconnecting transmission facilities. This results in a good possibility that useful paths between two users will survive when several nodes and transmission links are inoperative.
To make use of the requisite redundancy to enhance communications survivability, some method of controlling the facilities and selecting alternate (surviving) paths through the network is needed. To best use alternate paths to assure communications between any two users, it is desirable to provide for automatic selection of routing through surviving nodes and interconnecting transmission links in the damaged network. In order to maximize system survivability, the automatic routing system itself must be distributed, i.e., it must have no points of centralized vulnerability. Therefore, a capability is needed for each node to make local routing decisions for calls and messages originated by a user directly connected to the node or for calls and messages for which it is an intermediate connecting node (a tandem switching node). In order to accomplish distributed system control and call routing or message routing through the network in a straight-forward, effective manner with minimum delay, it is highly desirable to have nearly real-time network status information available at all nodes throughout the network. Such network status information tells which links are operational and which are not.
It is impractical to use individual messages to pass network status information from every node to every other node. Such a system would require the utilization of an unacceptably large portion of the network's communications capacity. Just transmitting the information needed to label the data to indicate to which individual transmission links each status indicator applies requires a large amount of transmission capacity.
In addition to a need to provide network status information throughout the network for use in call or message routing and system control, there is a need to provide a survivable message service for extremely important messages. This service is needed for priority messages of such importance that they sould be delivered to every node of the network over every existing (surviving) path.
Among the prior art are a number of patents which disclose inventions relating to the field of communications networks. For example, the Chasek U.S. Pat. No. 4,308,613 discloses a simplex data transmission system that includes a means for using alternate routing in case there is a failure in one of the communications links. The system incorporates end-of-message codes and no-message signals into the data transmission and detects the absence of any signal in the primary link. The Hemdal U.S. Pat. No. 4,022,982 discloses apparatus for rearranging a switching network to overcome an overload condition. The apparatus includes a memory unit for recording the actual network condition in a number of memory cells, each cell having a record of which network input and network output is interconnected via the link in question. The Stover U.S. Pat. No. 4,142,069 discloses a system that distributes a time reference to a plurality of interconnected nodes of a communications network for synchronizing the network and correcting each local node's time error. Information is passed between nodes to indicate the path the signal has taken and a weighing function is assigned to reflect the path taken. The Joel U.S. Pat. No. 4,317,193 discloses a switching network having a plurality of nodes through which various links can be established to interconnect the nodes utilizing the least busy path. A scanner and a scan counter memory is used to map the nodal use. The Paulish et al. U.S. Pat. No. 4,287,592 discloses a communications system between a plurality of loops of ring connected sets of nodes in which alternate routing can be accomplished. Primary and secondary functional addresses of the receiving station of a particular node are injected into an information packet and are utilized to locate the correct receiving station. The Graham U.S. Pat. No. 4,125,808 discloses a communications system comprised of a network of retransmission units, each of which is connected to a plurality of transmitting and base units. The system utilizes frequency-time co-channel addressing techniques and pulse-position modulation to select available communications links, and the various components of the system store identifying information sent by each entrant and store call status information in a network memory unit. The de Conasnor et al. U.S. Pat. No. 4,168,400 discloses a digital communication system having a plurality of interconnected stations, each station producing information, including addressing information, that is transmitted in packets. Each station can retransmit a message received from another station in a predefined priority order. The Nichols U.S. Pat. No. 4,144,414 discloses a multinode communications system having a frequency synchronization circuit and a mechanism for detecting transmission errors. The Hafner U.S. Pat. No. 4,081,612 discloses a digital telecommunications network having means for building up a routing address when only the call number is known and the location and network are unknown.